# 2249. 统计圆内格点数目
# 中等
# 相关标签
# 相关企业
# 提示
# 给你一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 表示网格上圆心为 (xi, yi) 且半径为 ri 的第 i 个圆，返回出现在 至少一个 圆内的 格点数目 。
#
# 注意：
#
# 格点 是指整数坐标对应的点。
# 圆周上的点 也被视为出现在圆内的点。
from typing import List


class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        ans = 0
        circles.sort(key=lambda c: -c[2])  # 按半径从大到小排序，这样能更早遇到包含 (i,j) 的圆
        max_x = max(c[0] + c[2] for c in circles)
        max_y = max(c[1] + c[2] for c in circles)
        for i in range(max_x + 1):
            for j in range(max_y + 1):
                for x, y, r in circles:
                    if (x - i) * (x - i) + (y - j) * (y - j) <= r * r:
                        ans += 1
                        break
        return ans
